home *** CD-ROM | disk | FTP | other *** search
-
- /* Copyright (C) 2009 Norman Solomon
- * e-mail: historytree.addon@yahoo.com
- *
- * The contents of this file are subject to the Mozilla Public License Version
- * 1.1 (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at http://www.mozilla.org/MPL/
- *
- * Software distributed under the License is distributed on an "AS IS" basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the License.
- */
-
- // ******************************************************************************************
- // ***** *****
- // ***** This JS file implements Sven Moen's algorithm to arrange a tree for tidy *****
- // ***** drawing. Sven's algorithm ALWAYS lays out the tree horizontally, but it *****
- // ***** has been adjusted here (with functions added) to layout a vertical tree *****
- // ***** -------------------------------------------------------------------------- *****
- // ***** *****
- // ***** FIRST THE CLASSES - Passed properties MUST be set when a class is created *****
- // ***** Java variable type declarations are shown in a comment above each class *****
- // ***** *****
- // ******************************************************************************************
-
- // ---------------------------------------------------------------
- // TreeNode objects are stored in the global gTreeNodes[] Array
- // (TreeNode p, TreeNode c, TreeNode s, int w, int h)
- // ---------------------------------------------------------------
- var TreeNode = function (p, c, s, w, h)
- {
- // ----------------------------------------------------------
- // Props needed for ANY implementation of Sven's algorithm
- // ----------------------------------------------------------
- this.parent = p;
- this.child = c;
- this.sibling = s;
-
- // Properties that determine node size and overall tree size
- this.width = w;
- this.height = h;
- this.border = 0;
-
- // Properties calculated in Sven's tArrLayout() method
- this.pos = new Point(0, 0);
- this.offset = new Point(0, 0);
- this.contour = new Polygon();
-
- // -------------------------------------------------------
- // Properties specific to this FF extension application
- // -------------------------------------------------------
- this.histNode = null; // Ref to this TreeNodes's associated HistoryNode
- this.isOpenPage = false; // Set = true if underlying web-page is open in FF
-
- this.inOpenTab = null; // Set = true if Tab root TreeNode is open in FF
- this.tabTreeSize = 0; // Number of TreeNode's in a Tab sub-tree
-
- this.childCopy = null; // Used to expand/contract sub-trees
- this.hiddenTreeSize = 0; // Size of hidden sub-tree below node
- this.hidden = false; // Set = true if this TreeNode is in hidden sub-tree
-
- // Props used to restore tree's overall state to its initial state
- this.parentBak = null;
- this.childBak = null;
- this.siblingBak = null;
-
- // Props for detection of mouse-click on TreeView node
- this.hidBtnWid = 0;
- this.btnPanelWid = 0;
- this.btnPanelX = 0;
-
- // Props for GridView image drawing and mouse-click detection
- this.gridViewImgX = 0;
- this.gridViewImgY = 0;
- this.gridViewImgWid = 0;
- this.gridViewTabNum = 0;
-
- // Description strings for text displayed inside this TreeNode
- this.histNodeDesc = ""; // Used to check whether descLine's are up to date
- this.descLine1 = ""; // Set in function setDescriptionLinesFor()
- this.descLine2 = ""; // Set in function setDescriptionLinesFor()
- }
-
- // -----------------------------------------------------------------------
- // Polylines are used to build the sub-tree contours around each TreeNode
- // (int dx, int dy, PolyLine link)
- // -----------------------------------------------------------------------
- var PolyLine = function (dx, dy, link)
- {
- this.dx = dx;
- this.dy = dy;
- this.link = link;
- }
-
- // -----------------------------------------------------------------------
- // Represents a polygon area for use in spacing/positioning calculations
- // *** No props are passed to the class instantiator when object created
- // -----------------------------------------------------------------------
- var Polygon = function ()
- {
- // Four Polyline objects
- this.lower_head;
- this.lower_tail;
- this.upper_head;
- this.upper_tail;
- }
-
- // -----------------------------------------------------------------------
- // JS equivalent of Java Point object (used by several functions below)
- // (int x, int y)
- // -----------------------------------------------------------------------
- var Point = function (x, y)
- {
- this.x = x;
- this.y = y;
- }
-
- // ******************************************************
- // ***** *****
- // ***** FUNCTIONS WRITTEN BY Sven Moen *****
- // ***** -------------------------------------- *****
- // ***** Java variable type declarations are *****
- // ***** shown in a comment above each method *****
- // ***** *****
- // ******************************************************
-
- // -----------------------------------------------------------
- // Lays out the tree node spacing by setting Node offsets
- // (TreeNode t)
- // -----------------------------------------------------------
- function tArrLayout(t)
- {
- var c; // TreeNode
-
- // ------------------------------------
- // Exit if the passed node is null
- if (t === null)
- return;
-
- // ***********************************
- // ******* RECURSIVE LOOP ********
- // ***********************************
- c = t.child;
- while (c != null)
- {
- tArrLayout(c);
- c = c.sibling;
- }
-
- // ------------------------------------
- // Set contour property of this node
- if (t.child !== null)
- // Create the contour around sub-tree below
- tArrAttachParent(t, tArrJoin(t));
- else
- // Create the contour round ONLY this leaf
- tArrLayoutLeaf(t);
- }
-
- // -----------------------------------------------------------
- // Attaches specified node to its children, setting offsets
- // (TreeNode t, int h)
- // -----------------------------------------------------------
- function tArrAttachParent(t, h)
- {
- var x, y1, y2;
-
- x = t.border + LEVEL_SPACE;
- y2 = (h - t.height) / 2 - t.border;
- y1 = y2 + t.height + (2 * t.border) - h;
-
- t.child.offset.x = x + t.width;
- t.child.offset.y = y1;
-
- // Set contour property of the passed node
- t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1, t.contour.upper_head));
- t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2, t.contour.lower_head));
- }
-
- // -----------------------------------------------------------
- // Sets passed nodes contour property using Polyline objects
- // (TreeNode t)
- // -----------------------------------------------------------
- function tArrLayoutLeaf(t)
- {
- // Draw a contour around leaf node & store it in the nodes contour property
- t.contour.upper_tail = new PolyLine(t.width + (2 * t.border), 0, null);
- t.contour.upper_head = t.contour.upper_tail;
- t.contour.lower_tail = new PolyLine(0, - t.height - (2 * t.border), null);
- t.contour.lower_head = new PolyLine(t.width + (2 * t.border), 0, t.contour.lower_tail);
- }
-
- // -----------------------------------------------------------
- // Merges t's children & returns height of resulting contour
- // (TreeNode t)
- // -----------------------------------------------------------
- function tArrJoin(t)
- {
- // *** NOTE - t is parent and c are it's children
- var c; // TreeNode
- var d, h, sum; // integers
-
- // --------------------------------------------
- // Set parent contour equal to child contour
- c = t.child;
- t.contour = c.contour;
-
- // --------------------------------------------
- // Initialize values used in loop
- //sum = h = c.height + 2 * c.border;
- h = c.height + (2 * c.border);
- sum = h;
-
- // --------------------------------------------
- // Loop round all children of parent t
- c = c.sibling;
- while(c != null)
- {
- d = tArrMerge(t.contour, c.contour);
- c.offset.y = d + h;
- c.offset.x = 0;
- h = c.height + (2 * c.border);
- sum += d + h;
-
- // Get next child
- c = c.sibling;
- }
- // ---------------------------------
- return sum;
- }
-
- // -------------------------------------------------------------------
- // Merges two polygons and returns total height of resulting polygon
- // (Polygon c1, Polygon c2)
- // -------------------------------------------------------------------
- function tArrMerge(c1, c2)
- {
- // integers
- var x = 0;
- var y = 0;
- var total = 0;
- var d;
-
- // Polylines
- var lower, upper, b;
-
- // --------------------------------------
- upper = c1.lower_head;
- lower = c2.upper_head;
-
- while(lower != null && upper != null)
- {
- // compute tArrOffset total
- d = tArrOffset(x, y, lower.dx, lower.dy, upper.dx, upper.dy);
- y += d;
- total += d;
-
- if (x + lower.dx <= upper.dx)
- {
- y += lower.dy;
- x += lower.dx;
- lower = lower.link;
- }
- else
- {
- y -= upper.dy;
- x -= upper.dx;
- upper = upper.link;
- }
- }
-
- // -------------------------------------------
- // store result in c1 (calls tArrBridge function)
- if (lower !== null)
- {
- b = tArrBridge(c1.upper_tail, 0, 0, lower, x, y);
- c1.upper_tail = (b.link != null) ? c2.upper_tail : b;
- c1.lower_tail = c2.lower_tail;
- }
- else // (upper)
- {
- b = tArrBridge(c2.lower_tail, x, y, upper, 0, 0);
-
- if (b.link === null)
- c1.lower_tail = b;
- }
-
- c1.lower_head = c2.lower_head;
-
- // -----------------------------------
- // Return the total
- return total;
- }
-
- // ------------------------------------------------------------------
- // Returns a value used to set contour - Only called from tArrMerge()
- // (PolyLine line1, int x1, int y1, PolyLine line2, int x2, int y2)
- // ------------------------------------------------------------------
- function tArrBridge(line1, x1, y1, line2, x2, y2)
- {
- var dy, dx, s; // integers
- var r; // Polyline
-
- dx = x2 + line2.dx - x1;
-
- if (line2.dx === 0)
- {
- dy = line2.dy;
- }
- else
- {
- s = dx * line2.dy;
- dy = s / line2.dx;
- }
-
- r = new PolyLine(dx, dy, line2.link);
- line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r);
-
- return r;
- }
-
- // ---------------------------------------------------------
- // Calculates the tArrOffset for specified points
- // (int p1, int p2, int a1, int a2, int b1, int b2)
- // ---------------------------------------------------------
- function tArrOffset(p1, p2, a1, a2, b1, b2)
- {
- var d, s, t; // integers
-
- if (b1 <= p1 || p1 + a1 <= 0)
- return 0;
-
- t = b1 * a2 - a1 * b2;
- // ----------------------
- if (t > 0)
- // ----------------------
- {
- if (p1 < 0)
- {
- s = p1 * a2;
- d = s / a1 - p2;
- }
- else if (p1 > 0)
- {
- s = p1 * b2;
- d = s / b1 - p2;
- }
- else
- {
- d = -p2;
- }
- }
- // ----------------------
- else if (b1 < p1 + a1)
- // ----------------------
- {
- s = (b1 - p1) * a2;
- d = b2 - (p2 + s / a1);
- }
- // ----------------------
- else if (b1 > p1 + a1)
- // ----------------------
- {
- s = (a1 + p1) * b2;
- d = s / b1 - (p2 + a2);
- }
- // ----------------------
- else
- // ----------------------
- {
- d = b2 - (p2 + a2);
- }
-
- // ======================
- if (d > 0)
- return d;
- else
- return 0;
- }
-
- // -----------------------------------------------------------------
- // Calculates pos.x and pos.y for all nodes by traversing the tree
- // and using the nodes offset.x and offset.y values
- // (TreeNode t, int off_x, int off_y)
- // -----------------------------------------------------------------
- function tArrPlantTree(t, off_x, off_y)
- {
- var c, s; // TreeNodes
- var cur_y; // integer
-
- // --------------------------------
- // Set node screen (x,y) position
- t.pos.x = off_x + t.offset.x;
- t.pos.y = off_y + t.offset.y;
-
- // --------------------------------
- // Set global for whole tree
- if (t.pos.y < gTreeMinY)
- gTreeMinY = t.pos.y;
-
- // --------------------------------
- // Plant child node
- c = t.child;
- if(c !== null)
- {
- // ***********************************
- // ******* RECURSIVE CALL ********
- // ***********************************
- tArrPlantTree(c, t.pos.x, t.pos.y);
-
- // Plant sibling nodes
- s = c.sibling;
- cur_y = t.pos.y + c.offset.y;
-
- while(s != null)
- {
- // ***********************************
- // ******* RECURSIVE CALL ********
- // ***********************************
- tArrPlantTree(s, t.pos.x + c.offset.x, cur_y);
- cur_y += s.offset.y;
- s = s.sibling;
- }
- }
- }
-
-
- // ********************************************************************************
- // ***** *****
- // ***** PROCEDURES ADDED TO Sven Moen's algorithm TO ALLOW VERTICAL *****
- // ***** TREES TO BE LAID OUT TIDILY - INCLUDING SOME USEFUL UTILITY *****
- // ***** FUNCTIONS FOR ANY IMPLEMENTATION OF THE Sven Moen algorithm *****
- // ***** ------------------------------------------------------------------ *****
- // ***** Java type declarations are shown in a comment above each method *****
- // ***** *****
- // ********************************************************************************
-
- // ----------------------------------------------------------------------------
- // 1) Adjusts horizontal tree position so it fits snugly in top left corner
- // 2) Changes tree to vertical orientation by swapping all TreeNode.(x,y)
- // *** NOTE - Sven Moen's algorithm ALWAYS lays out tree horizontally
- // (TreeNode root)
- // ----------------------------------------------------------------------------
- function changeTreeToVerticalLayout(root)
- {
- // Initialize global variable
- gTreeMinY = 0; // integer
-
- // Private variables
- var node; // TreeNode
- var tempX; // integer
- var yAddOn = 0;
- if (root.child !== null)
- {
- node = root.child;
- yAddOn = node.height - BOX_HEIGHT;
- }
-
- // -----------------------------------------------
- // *** NOTE - tArrPlantTree is a recursive procedure
- tArrPlantTree(root, 0, 0);
- tArrPlantTree(root, 0, Math.abs(gTreeMinY));
-
- // Change tree to vertical orientation by swapping all TreeNode.(x,y)
- for (var i = 0; i < gTreeNodes.length; i++)
- {
- // Get TreeNode from gTreeNodes[] and swap (x,y)
- node = gTreeNodes[i];
- if (!node.hidden)
- {
- // Swap x and y co-ordinates
- tempX = node.pos.x;
- node.pos.x = node.pos.y;
- node.pos.y = tempX;
-
- // Adjust for taller Tab roots
- if (node.height > BOX_HEIGHT)
- node.pos.x += Math.round(yAddOn / 2);
- else if (node !== root)
- node.pos.y += yAddOn;
- }
- }
- }
-
- // ==========================================================
- // Sets left/top border for all TreeNode's drawn on gCanvas
- // (int leftBord, int topBord)
- // ----------------------------------------------------------
- function setLeftAndTopBorderForWholeTree(leftBord, topBord)
- {
- var node; // TreeNode
- for (var i = 0; i < gTreeNodes.length; i++)
- {
- // Get TreeNode from gTreeNodes[]
- node = gTreeNodes[i];
- if (!node.hidden)
- {
- node.pos.x += leftBord;
- node.pos.y += topBord;
- }
- }
- }
-
- // ===============================================================
- // Sets border for all nodes - which determines overall tree size
- // (int bordSize)
- // ---------------------------------------------------------------
- function setBorderForAllNodes(bordSize)
- {
- var node; // TreeNode
- for (var i = 0; i < gTreeNodes.length; i++)
- {
- // Get TreeNode from gTreeNodes[] and set its border
- node = gTreeNodes[i];
- node.border = bordSize;
- }
- }
-
- // ============================================================
- // Returns width and height of the whole tree as a Point(x,y)
- // ------------------------------------------------------------
- function treeDimensions()
- {
- // TreeNode and 6 integers
- var node;
- var minX = 0;
- var maxX = 0;
- var minY = 0;
- var maxY = 0;
- var tWid = 0;
- var tHgt = 0;
-
- // -----------------------------------------
- for (var i = 0; i < gTreeNodes.length; i++)
- {
- // Get TreeNode from gTreeNodes[]
- node = gTreeNodes[i];
- if (!node.hidden)
- {
- // Set max/min XY for whole tree
- if (node.pos.x + node.width > maxX)
- maxX = node.pos.x + node.width;
-
- if (node.pos.x < minX)
- minX = node.pos.x;
-
- if (node.pos.y + node.height > maxY)
- maxY = node.pos.y + node.height;
-
- if (node.pos.y < minY)
- minY = node.pos.y;
- }
- }
-
- // Set tree width and height
- tWid = Math.ceil(maxX - minX);
- tHgt = Math.ceil(maxY - minY);
-
- // Return width and height as a Point(x,y)
- return new Point(tWid, tHgt);
- }
-
- // ===============================================================
- // Sets node.hidden for all nodes in sub-tree below passed root
- // Returns the number of nodes in the sub-tree below passed root
- // (TreeNode root, boolean hide)
- // ---------------------------------------------------------------
- function markSubTreeAsHiddenOrVisible(root, hide)
- {
- // Initialize tree size global variable
- gSubTreeSize = 0;
-
- // Run recursive procedure that increments global var
- walkSubTree(root, hide);
-
- // Recursion complete - So return tree size
- return gSubTreeSize;
- }
-
- // ============================================================
- // RECURSIVE routine to visit all TreeNode's below passed root
- // (TreeNode t, boolean hide)
- // ------------------------------------------------------------
- function walkSubTree(t, hide)
- {
- var c, s; // TreeNodes
-
- // --------------------------------------
- // Mark TreeNode as hidden or visible
- t.hidden = hide;
-
- // Add to count of num TreeNode's in sub-tree
- if (t.hiddenTreeSize > 0)
- gSubTreeSize += t.hiddenTreeSize;
- else
- gSubTreeSize ++;
-
- // --------------------------------------
- // Move to next TreeNode in sub-tree
- c = t.child;
- if(c !== null)
- {
- // ***********************************
- // ******* RECURSIVE CALL ********
- // ***********************************
- walkSubTree(c, hide);
- s = c.sibling;
-
- while(s != null)
- {
- // ***********************************
- // ******* RECURSIVE CALL ********
- // ***********************************
- walkSubTree(s, hide);
- s = s.sibling;
- }
- }
- }
-